CHAP, vii] BINOMIAL CONGRUENCES. 207
case p = 8n-|-5; but in general no such direct solution is known, and it is best to represent some multiple of p by the form y2+az2.
If we have found 6 such that 02+a is divisible by the prime p, not dividing a, we readily solve z2-fa=0 (mod pn). For, from
, (02+a)n=r2+as2,
r2+as2 is divisible by pn. Now s is not divisible by p. Thus we may take r = s£-fpn2/, whence x2+a is divisible by pn. [Cf. Tchebychef, Theorie der Congruenzen, §30.]
The case of any composite modulus N is easily reduced to the preceding (end of Lagrange's153 paper). Legendre proved that, if N is odd and prime to a, the number of solutions of o;2+« = 0 (mod N) is 21"1 where i is the number of distinct prime factors of N; the, same is true for modulus 2N. Henceforth let N be odd or the double of an odd number and let d be the g. c. d. of N and a. If d has no square factor, the congruence has 21"1 roots, where i is the number of distinct odd prime factors of N not dividing a. But if d=co^2, where w has no square factor, the congruence has 21""1^ roots where i is the number of distinct odd prime factors of N/d.
C. F. Gauss157 treated congruence (1) by the use of indices. However, we can give a direct solution (arts. 66-68) when a root is known to be congruent to a power of B. For, by (1) and x=zBk, Bz~Bkn. If therefore a relation of the last type is known, a root of (1) is Bk. The condition for the relation is l=&n (mod 0, where t is the exponent to which B belongs modulo p. It is shown that t must divide m = (p — l)/n. We may discard from ra any factor of n; if the resulting number is m/q, the unique solution k of l=/bn. (mod m/q) is the desired /c. [Cf. Poinsot165.]
Gauss (arts. 101-5) gave the usual method of reducing the solution of x2=A (mod ra) for any composite modulus to the case of a prime modulus and gave the number of roots modulo pn in the various possible subcases. His well-known and practical "method of exclusion" (arts. 319-322) employs successive small powers of primes as moduli. Another method (arts. 327-8) is based on the theory of binary quadratic forms [cf. Smith170].
The congruence ax2-i-bx-{-c=Q (mod ra) is reduced (art. 152) to ?/2=62 — 4ac (mod 4aw). For each root y, it remains to solve 2ax-\-b=y (mod 4am) .
Gauss158 showed in a somewhat incomplete posthumous paper that, if t is a prime and F~l(t — 1) =aa^. . ., where a, b, . . . are distinct primes, the solution of xn= 1 (mod f ) may be made to depend upon the solution of a congruences of degree a, /3 congruences of degree 5, etc. Use is made of the periods formed of the primitive roots of the congruence, as in Gauss' theory of roots of unity.
Legendre159 solved ar+a=0 (mod 2W) when a is of the form — 1 =p8a by
"'Disquis. Arith., 1801, Arts. 60-65.
l«\Vcrkc, 2, 1863, 199-211. Maser's German transl. of Gauss' Disq. Arith., etc., 1880, 589-601
(comments, p. 683). iG»T}i<Wip rlnfl nnmhros. pHL 2. 1808. nn. 358-fiO (Nos. 350-2}. Maser. 2. 1893. 25-7.